package net.tp.algo.sort;

/**
 * User: Trung
 * Date: 4/27/13
 * Time: 10:35 AM
 */
public class StringMsdRadixSort {

    public static final int R = 256;

    public static void sort(String[] data, boolean asc) {
        if (asc) {
            sort(data, 0, 0, data.length - 1);
        }
        else {
            sortDesc(data, 0, 0, data.length - 1);
        }
    }

    private static void sort(String[] data, int pos, int lo, int hi) {

        if (lo >= hi || (pos > 0 && charAt(data[lo], pos-1) == '\0')) {
            return;
        }

        String[] aux = new String[hi - lo + 1];

        int[] counts = new int[R + 1];
        for (int i = lo; i <= hi; i++) {
            int c = charAt(data[i], pos);
            counts[c]++;
        }

        for (int i = 1; i < R + 1; i++) {
            counts[i] += counts[i-1];
        }

        for (int i = hi; i >= lo; i--) {
            aux[--counts[charAt(data[i], pos)]] = data[i];
        }

        for (int i = lo; i <= hi; i++) {
            data[i] = aux[i - lo];
        }

        for (int i = 0; i < R; i++) {
            sort(data, pos+1, counts[i] + lo, counts[i+1] + lo - 1);
        }

    }

    private static void sortDesc(String[] data, int pos, int lo, int hi) {
        if (lo >= hi || (pos > 0 && charAt(data[lo], pos-1) == '\0')) {
            return;
        }

        String[] aux = new String[hi - lo + 1];

        int[] counts = new int[R+1];
        for (int i = lo; i <= hi; i++) {
            counts[charAt(data[i], pos) + 1]++; // +1 to accommodate lower bound
        }

        for (int i = R - 1; i >= 0; i--) {
            counts[i] += counts[i+1];
        }

        for (int i = hi; i >= lo; i--) {
            aux[--counts[charAt(data[i], pos) + 1]] = data[i];
        }

        for (int i = lo; i <= hi; i++) {
            data[i] = aux[i - lo];
        }

        for (int i = 0; i < R; i++) {
            sortDesc(data, pos+1, counts[i+1] + lo, counts[i] + lo - 1);
        }

    }


    private static char charAt(String text, int i) {
        return i < text.length() ? text.charAt(i) : '\0';
    }

}
